Efficient detection techniques for the one-dimensional inter-symbol interference (1-D ISI) problem, such as Viterbi equalization and decision-feedback equalization (DFE), have been well understood for almost thirty years and are in widespread use in communications devices. The complexity per bit of optimal detection procedures for finite-span 1-D ISI channels depends only on the duration of the channel response and is independent of the number of bits transmitted. However, for channels with more that one dimension, the complexity (per bit) of optimal detection becomes infinite as the extent of the multi-dimensional data set is allowed to become infinite, and there is no known optimal detection procedure with a constant per-bit complexity. This is true in particular with respect to two-dimensional inter-symbol interference (2-D ISI) channels.
The lack of an optimal detection procedure for 2-D ISI channels is problematic, since 2-D ISI channels are becoming of increasing interest in data storage and transmission. Current applications of low-complexity 2-D ISI detection techniques include high density page and volume oriented storage and digital imaging. 2-D ISI detection techniques also facilitate fast parallel readout of data from such memory devices. In the future, magnetic and optical recording channels, which have typically been modeled as 1-D, may require 2-D models to account for the interference from adjacent tracks as the recording density is increased. The lack of an optimal detection procedure for 2-D ISI thus poses a major obstacle for successful holographic and other data storage and imaging as well as signal processing.
The problem of detection of the 2-D ISI channel has been approached in several ways. For example, linear filtering has been employed to mitigate the effects of 2-D ISI. Also, attempts have been made to extend the applicability of 1-D ISI channel detection methods to the detection of 2-D ISI channels. In particular, multi-stage and iterative methods have been applied to the problem. For example, it has been suggested to apply the Viterbi Algorithm (VA) on each row of a multi-row two-dimensional image and subtracting out ISI from previously detected rows based on estimate(s) from earlier decisions, in effect, using the VA in one dimension and decision feedback (DF) in the other. Further for example, it has been suggested to apply threshold detection, and then to improve the detection estimate by an iterative post-processing procedure where bits are flipped if a lower distance estimate is obtained.
Despite these and other attempts to address the problem of detecting the 2-D ISI channel, none of these methodologies has proven to be satisfactory. For example, where linear filtering has been employed, noise enhancement has severely degraded performance, particularly with respect to channels having nulls. Further, the application of multi-stage and iterative methods to date have proven to be unsatisfactory. In particular, such methods have proven to be of limited value in terms of their level of performance and accuracy, and/or have proven to require excessive computation, or both. Consequently, present methods for detecting 2-D ISI channels are impractical.
Therefore, it would be advantageous if a new method and system could be developed to allow for detection of 2-D ISI channels. In particular, it would be advantageous if such new method and system could better approach theoretical limits of performance and at the same time be implemented without excessive computational requirements.